package com.wrial.face;
/*
 * @Author  Wrial
 * @Date Created in 18:46 2020/8/18
 * @Description 一个包含1-N数字的数组中，有一个数字丢失了，如何快速的找出它？
 * （要求空间负责度为O(1)，时间负责度尽可能低）
 *
 * 思路：
 * 这个题可以根据这个N计算出总和，然后再计算出当前数字的和，然后相减就可得到缺少数据
 */

public class FindLost {

//    public Long findLost(int N, int[] nums) {
////        Long sum = 0l;
////        for (int i = 1; i <= N; i++) {
////            sum += i;
////        }
////        Long curSum = 0l;
////        for (int num : nums) {
////            curSum += num;
////        }
////        return sum - curSum;
////    }

    /**
     * 可以使用数学公式对求和过程进行优化
     * （首项+末项）*项数/2
     * @param N
     * @param nums
     * @return
     */
    public Long findLost(int N, int[] nums) {
        Long sum = 0l;
        sum = (1 + N) * N / 2l;
        Long curSum = 0l;
        for (int num : nums) {
            curSum += num;
        }
        return sum - curSum;
    }
}
